// new 方法实现
/**
 * 先创建一个空对象，将空对象的__proto__属性指向构造函数的原型对象
 * 将函数指向创建的空对象，并传递参数，修改空对象
 * 修改之后如果是一个object，那就直接返回，否则返回一个v空对象
 */
function _new(fn, ...arg) {
    let obj = Object.create(fn.prototype);
    let ret = fn.apply(obj, args);
    return ret instanceof Object ? ret : obj;
}

// map 
Array.prototype.Mymap = function (fn, context) {
    let arr = Array.prototype.slice.call(this);
    var mergeArr = [];
    for (let i = 0; i < arr.length; i++) {
        mergeArr.push(fn.call(context, arr[i], i, this));
    }
    return mergeArr;
}
console.log([1,2,3].Mymap(m => m*2));

// reduce
Array.prototype.myReduce = function (fn, startVal) {
    let arr = Array.prototype.slice.call(this);
    let res = startVal || arr[0];
    let startIndex = startVal ? 0 : 1;
    for(let i = startIndex; i < arr.length; i++) {
        res = fn.call(null, res, arr[i], i, this);
    }
    return res;
}
console.log([1,2,3].myReduce((a, b) => a + b));

// call/apply
// call方法将...args变为args即可
Function.prototype.myApply = function (context = window, ...args) {
    let func = this;
    let fn = Symbol();
    context[fn] = func;
    
    let res = context[fn](...args);
    delete context[fn];
    return res;
}
let obj1 = {name: 'aaa'}
function f1(name) {
    return this.name;
}
console.log(f1.myApply(obj1, '11'), 'apply');

// bind
Function.prototype.myBind = function (context, ...args) {
    let self = this;
    let fBound = function () {
        return self.apply(context, args);
    }
    fBound.prototype = Object.create(this.prototype);
    return fBound;
}
let obj2 = {name: 'aaa'};
function f2() {console.log(this.name, 'bind')}
let func = f2.myBind(obj2, '222');
func();


// Object.create
function create(proto) {
    function F() {};
    F.prototype = proto;
    F.prototype.constructor = F;
    
    return new F();
}

// instanceof
function myInstanceof(left, right) {
    let proto = Object.getPrototypeOf(left);
    while(true) {
        if (proto == null) return false;
        if (proto == right.prototype) return true;
        proto = Object.getPrototypeOf(proto);
    }
}
function o2() {}
function o3() {}
let obj3 = new o2(), obj4  = new o3();
console.log(myInstanceof(obj3, o2), myInstanceof(obj4, o2), 'myInstanceof');

// flat方法实现
let arr = [1,[2,[3,[4,5]]], 6];
let str = JSON.stringify(arr);
// 方法1：
console.log(JSON.parse('[' + str.replace(/(\[|\])/g, '') + ']'));
// 方法二
console.log(arr.flat(Infinity));
// 方法三
function flat1(arr) {
    while (arr.some(m => Array.isArray(m))) {
        arr = [].concat(...arr);
    }
    return arr;
}
console.log(flat1(arr), 'flat1')
// 方法四
function flat2(arr) {
    return arr.reduce((acc, m) => Array.isArray(m) ? [...acc, ...flat2(m)] : [...acc, m], []);
}
console.log(flat2(arr), 'flat2');

// 防抖
const deBounce = (fn, delay = 300) => {
    let timer = null;
    return (...args) => {
        clearTimeout(timer);
        setTimeout(() => {
            fn.apply(this, args);
        }, delay);
    }
}

// 节流
const throttle = (fn, daelay = 500) => {
    let flag = true;
    return (...args) => {
        if (!flag) return;
        flag = false;
        setTimeout(() => {
            fn.apply(this, args);
            flag = true;
        }, delay);
    }
}

// 深克隆
// 这里也可以使用Map，但是为了垃圾回收，减少内存消耗，所以使用了WeakMap
function cloneDeep (target, map = new WeakMap()) {
    if (typeof target === 'object') {
        let cloneTarget = Array.isArray(target) ? [] : {};
        if (map.get(target)) {
            return target;
        }
        map.set(target, cloneTarget);
        for(const key in target) {
            cloneTarget[key] = cloneDeep(target[key], map);
        }
        return cloneTarget;
    } else {
        return target;
    }
}
    
const symbolName = Symbol();
const oo = {
    a: 1,
    b: ['2'],
    c: {k: 8},
    d: () => {},
    e: {
        n: {
            p: 999
        }
    },
    [symbolName]: 111,
    regexp: /w+/g,
}
const cloneO = {
    ...oo,
    f: oo
};
const cloneO2 = cloneDeep(cloneO);
console.log(cloneO2, 'cloneO2');
cloneO2.c.k = 10;
console.log(cloneO, cloneO2, 'cloneO21');


// 实现add(1)(2)(3) ------不对？
const sum = (...args) => args.reduce((a, b) => a + b);
function add1() {
    let args = [].slice.call(arguments);
    let fn = function(){
        let fn_args = [].slice.call(arguments);
        return add1.apply(null,args.concat(fn_args));
    }
    fn.toString = function(){
        return args.reduce((a,b)=>a+b);
    }
    return fn;
}
console.log(add1(1)(2)(3), 'add1');

// 实现add(1)(2)(3)()
function currying2(func) {
    const args = [];
    return function result(...rest) {
        if (rest.length === 0) {
          return func(...args);
        } else {
          args.push(...rest);
        	return result;
        }
    }
}
const add2 = currying2(sum);
console.log(add2(1)(2)(3)(), 'add2');

// sleep
function sleep(fn, delay) {
    return new Promise((resolve, reject) => {
        setTimeout(fn,  delay);
    })
}

// 排序算法
// 冒泡排序
function bubbleSort(arr){
    for (let i = 0; i < arr.length; i++) {
        for (let j = 0; j < arr.length - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                let temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
    return arr;
}
console.log(bubbleSort([2,3,6,4,1,7]));

// 快速排序
function quickSort(arr) {
    if (arr.length <= 1) return arr;
    let mid = Math.floor(arr.length / 2);
    let midVal = arr.splice(mid, 1)[0];
    let left = [];
    let right = [];
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] < midVal) {
            left.push(arr[i]);
        } else {
            right.push(arr[i]);
        }
    }
    return quickSort(left).concat([midVal], quickSort(right));
}
console.log(quickSort([2,3,6,4,1,7]), 'quickSort');

// lazyMan
class LazyManClass {
    constructor(name) {
        this.name = name;
        this.queue = [];
        console.log(`Hi I am ${name}`);
        setTimeout(() => {
            this.next();
        }, 0);
    }

    next () {
        const fn = this.queue.shift();
        fn && fn();
    }

    sleep(time) {
        const fn = () => {
            setTimeout(() => {
                console.log(`等待了${time}秒`);
                this.next();
            }, time);
        }
        this.queue.push(fn);
        return this;
    }

    eat(food) {
        const fn = () => {
            console.log(`I am eating ${food}`);
            this.next();
        }
        this.queue.push(fn);
        return this;
    }
}

function LazyMan(name) {
    return new LazyManClass(name);
}
LazyMan('Tony').sleep(1000).eat('lunch');

// 交集、并集、差集
const arr1 = [1,2,3,4,5],
      arr2 = [5,6,7,8,9],
      arr1Set = new Set(arr1),
      arr2Set = new Set(arr2);
// 交集
let intersection = arr1.filter(item => arr2Set.has(item));
// 并集
let union = Array.from(new Set([...arr1, ...arr2]));
// 差集
let diff = arr1.filter(item => !arr2Set.has(item));
console.log(intersection, union, diff, '交集、并集、差集');

// ’AbC' 变成 'aBc' 
function transformStr(str) {
    return [].map.call(str, (item) => {
        return /[a-z]/.test(item) ? item.toUpperCase() : item.toLowerCase();
    }).join('');
}

console.log(transformStr('AbC'))

// 实现一个字符串匹配算法，从长度为 n 的字符串 S 中，查找是否存在字符串 T，T 的长度是 m，若存在返回所在位置
const find = (s,t) => {
    if (s.length < t.length) return -1;
    for (let i = 0;i < s.length; i++) {
        if (s.substr(i, t.length) == t) return i;
    }
    return -1;
}
const s = 'asdfg', t = 'dfg';
console.log(find(s, t));

// proxy实现数据绑定 (mvvm.html)

// 旋转数组, 从第index元素宣旋转
function rotate(arr, index) {
    for(let i = 0; i < index; i++) {
        arr.unshift(arr.pop());
    }
    return arr;
}
const rotateArr = [1, 2, 3, 4, 5, 6, 7], k = 3;
console.log(rotate(rotateArr, k));

// 金钱分割
// 德国以 . 分割金钱, 转到德国当地格式化方案即可
console.log(10000000000..toLocaleString('de-DE'));

// 寻找字符空隙加 .
console.log('10000000000'.replace(/\B(?=(\d{3})+(?!\d))/g, '.'));

// 寻找数字并在其后面加 . 
console.log('10000000000'.replace(/(\d)(?=(\d{3})+\b)/g, '$1.'));

// 用 setTimeout 实现 setInterval，阐述实现的效果与 setInterval 的差异
function mySetInterval() {
    mySetInterval.timer = setTimeout(() => {
        arguments[0]()
        mySetInterval(...arguments)
    }, arguments[1])
}

mySetInterval.clear = function() {
    clearTimeout(mySetInterval.timer)
}

mySetInterval(() => {
    console.log(11111)
}, 1000)

setTimeout(() => {
    // 5s 后清理
    mySetInterval.clear()
}, 5000);

// 字符串中出现最多的字符
'aaasdofjaopfjopaiiisjssfopiasdfffff'.match(/(.)\1+/g)

// * 编程题，写个程序把 entry 转换成如下对象
// var entry = {
//     'a.b.c.dd': 'abcdd',
//     'a.d.xx': 'adxx',
//     'a.e': 'ae'
//   }
  
  // 要求转换成如下对象
//   var output = {
//     a: {
//       b: {
//         c: {
//           dd: 'abcdd'
//         }
//       },
//       d: {
//         xx: 'adxx'
//       },
//       e: 'ae'
//     }
//   }
var entry = {
    'a.b.c.dd': 'abcdd',
    'a.d.xx': 'adxx',
    'a.e': 'ae'
};

function map(entry) {
const obj = Object.create(null);
for (const key in entry) {
    const keymap = key.split('.');
    set(obj, keymap, entry[key])
}
return obj;
}

function set(obj, map, val) {
let tmp;
if (!obj[map[0]]) obj[map[0]] = Object.create(null);
tmp = obj[map[0]];
for (let i = 1; i < map.length; i++) {
    if (!tmp[map[i]]) tmp[map[i]] = map.length - 1 === i ? val : Object.create(null);
    tmp = tmp[map[i]];
}
}
console.log(map(entry));

// 编程题，写个程序把 entry 转换成如下对象,与上面相反
// var entry = {
//     a: {
//       b: {
//         c: {
//           dd: 'abcdd'
//         }
//       },
//       d: {
//         xx: 'adxx'
//       },
//       e: 'ae'
//     }
//   }
// 要求转换成如下对象
// var output = {
//     'a.b.c.dd': 'abcdd',
//     'a.d.xx': 'adxx',
//     'a.e': 'ae'
// }
function flatObj(obj, parentKey = "", result = {}) {
    for (const key in obj) {
        if (obj.hasOwnProperty(key)) {
        let keyName = `${parentKey}${key}`;
        if (typeof obj[key] === 'object')
            flatObj(obj[key], keyName+".", result)
        else
            result[keyName] = obj[key];
        }
    }
    return result;
}

// 获取url参数
new URLSearchParams('https://www.xx.cn/api?keyword=&level1=&local_batch_id=&elective=800,700&local_province_id=33').get('elective')

// 实现模糊搜索结果的关键词高亮显示 light.html

// 实现 convert 方法，把原始 list 转换成树形结构，要求尽可能降低时间复杂度
// 原始 list 如下
let list =[
    {id:1,name:'部门A',parentId:0},
    {id:2,name:'部门B',parentId:0},
    {id:3,name:'部门C',parentId:1},
    {id:4,name:'部门D',parentId:1},
    {id:5,name:'部门E',parentId:2},
    {id:6,name:'部门F',parentId:3},
    {id:7,name:'部门G',parentId:2},
    {id:8,name:'部门H',parentId:4}
];
const result = convert(list, ...);

// 转换后的结果如下
let result = [
    {
      id: 1,
      name: '部门A',
      parentId: 0,
      children: [
        {
          id: 3,
          name: '部门C',
          parentId: 1,
          children: [
            {
              id: 6,
              name: '部门F',
              parentId: 3
            }, {
              id: 16,
              name: '部门L',
              parentId: 3
            }
          ]
        },
        {
          id: 4,
          name: '部门D',
          parentId: 1,
          children: [
            {
              id: 8,
              name: '部门H',
              parentId: 4
            }
          ]
        }
      ]
    },
  ···
];

function convert(list) {
	const res = [];
	const map = list.reduce((res, v) => (res[v.id] = v, res), {});
	for (const item of list) {
		if (item.parentId === 0) {
			res.push(item);
			continue;
		}
		if (item.parentId in map) {
			const parent = map[item.parentId];
			parent.children = parent.children || [];
			parent.children.push(item);
		}
	}
	return res;
}

// 继承 寄生组合式
function extend(subClass, superClass) {
    var F = function() {};
    F.prototype = superClass.prototype;
    subClass.prototype = new F(); 
    subClass.prototype.constructor = subClass;
  
    subClass.superclass = superClass.prototype;
    if(superClass.prototype.constructor == Object.prototype.constructor) {
      superClass.prototype.constructor = superClass;
    }
}

// eventemit
class EmiterEvent {
    constructor() {
      this._event = {};
    }
  
    _isFunction(fn) {
      return Object.prototype.toString.call(fn) === '[object Function]'
        ? fn
        : () => {};
    }
  
    addlisternerEvent(type, fn) {
      let callback = this._isFunction(fn);
      if (!this._event[type]) {
        this._event[type] = [callback];
      } else {
        this._event[type].push(callback);
      }
    }
  
    emit(type, ...args) {
      if (!this._event[type]) {
        throw Error(`${type} event not found`);
        return;
      }
  
      for (let i = 0; i < this._event[type].length; i++) {
        let fn = this._event[type][i];
        fn.call(this, ...args);
      }
    }
  
    removelistenerEvent(type, fn) {
      let callback = this._isFunction(fn);
      delete this._event[type];
      callback();
    }
  }
  
  const ee = new EmiterEvent();
  ee.addlisternerEvent('change', function (...args) {
    console.log(args, 'change1');
  });
  ee.addlisternerEvent('change', function (...args) {
    console.log(args, 'change2');
  });
  ee.emit('change', 'str');
  ee.removelistenerEvent('change', function (...args) {
    console.log(`change已删除`);
  });
  ee.emit('change', 'str');

// promise
class Promise2 {
    constructor(callbackfn) {
      this.value = '';
      this.status = 'pending';
      this.fullfiledArgs = [];
      this.rejectedArgs = [];
  
      let resolveFn = (value) => {
        if (this.status == 'pending') {
          setTimeout(() => {
            this.status = 'fullfiled';
            this.value = value;
            this.fullfiledArgs.forEach((item) => item(this.value));
          });
        }
      };
  
      let rejectFn = (value) => {
        if (this.status == 'pending') {
          setTimeout(() => {
            this.status = 'rejected';
            this.value = value;
            this.rejectedArgs.forEach((item) => item(this.value));
          });
        }
      };
  
      try {
        callbackfn(resolveFn, rejectFn);
      } catch (err) {
        rejectFn(err);
      }
    }
  
    then(resolveCb, rejectCb) {
      if (typeof resolveCb != 'function') {
        resolveCb = (res) => res;
      }
      if (typeof rejectCb != 'function') {
        rejectCb = (res) => res;
      }
      return new Promise2((resolve, reject) => {
        this.fullfiledArgs.push(() => {
          try {
            let val = resolveCb(this.value);
            return val instanceof Promise2
              ? val.then(resolve, reject)
              : resolve(val);
          } catch (err) {
            reject(err);
          }
        });
  
        this.rejectedArgs.push(() => {
          try {
            let val = rejectCb(this.value);
            return val instanceof Promise2
              ? val.then(resolve, reject)
              : resolve(val);
          } catch (err) {
            reject(err);
          }
        });
      });
    }
  
    catch(callback) {
      return this.then(null, callback);
    }
}
let p1 = new Promise2((resolve, reject) => {
setTimeout(() => {
    Math.random() < 0.5 ? resolve(100) : reject(-100);
}, 1000);
});

let p2 = p1.then(
(result) => {
    console.log(result + 100);
},
(err) => {
    console.log(err - 50);
}
);

// 判断两个对象是否相等（阿里面试题）
function ifCompare(object1, object2) {
    var o1keys = Object.keys(object1);
    var o2keys = Object.keys(object2);
    if (o2keys.length !== o1keys.length) return false;
    for (let i = 0; i <= o1keys.length - 1; i++) {
        let key = o1keys[i];
        if (!o2keys.includes(key)) return false;
        if (object2[key] !== object1[key]) return false;
    }
    return true;
}

// 二叉树遍历(前序，中序，后序)，见算法题

// 字符串数组排序['nbs', 'ab', 'iw'] (腾讯面试题目)

